#include "Tank.h"
#include <string.h>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <list>
using namespace std;
//请勿修改以上头文件
/*

 您可以在这里添加您所需头文件

 */
#include "core.h"
#include "utils.h"

void markChoiceType(list<Choice>& ls, char type) {
	list<Choice>::iterator itr = ls.begin();
	while (itr != ls.end()) {
		itr->__type = type;
		itr++;
	}
}

void printOrder(Order& o) {
	fout << "{type:";

	if (o.type == STOP) {
		fout << "STOP";
	} else if (o.type == GOUP) {
		fout << "↑";
	} else if (o.type == GODOWN) {
		fout << "↓";
	} else if (o.type == GOLEFT) {
		fout << "←";
	} else if (o.type == GORIGHT) {
		fout << "→";
	} else if (o.type == FIRE) {
		fout << "Fire";
	} else {
		fout << "ERROR_ORDER_TYPE";
	}

	fout << ",row:" << o.row << ",col:" << o.col << "}";
}

void printChoice(Choice& c) {
	fout << "{order:";
	printOrder(c.order);
	fout << ",takeSourceStep:" << c.takeSourceStep << ",destination:"
			<< c.destination;
	fout << ",willDie:" << boolChr(c.willDie) << ",willKill:" << boolChr(
			c.willKill) << ",__weight:" << c.__weight << ",__type:" << c.__type
			<< "}";
}

void printResourceNeedCapture() {
	fout << "ResourceNeedCapture";
	for (int i = 0; i < MAX_SOURCE_NUM + 1; i++) {
		fout << "(" << i << "," << resourceNeedCapture[i] << ")";
	}
	fout << endl;
}

void printDestination() {
	fout << "Destination";
	for (int i = 0; i < MAX_TANK_NUM; i++)
		fout << "(" << i << "," << destination[i] << ")";
	fout << endl;
}

void printList(list<Item> list_) {
	fout << "openList";
	for (list<Item>::iterator it = list_.begin(); it != list_.end(); it++)
		fout << "F:" << (*it).F << " G；" << (*it).G << " H: " << (*it).H
				<< " (" << (*it).row << "," << (*it).col << ")  ";
	fout << endl;
}
bool IsOk(short row, short col) {
	if ((1 <= row && row <= MAP_WIDTH) && (1 <= col && col <= MAP_HEIGHT))
		return 1;
	return 0;
}
bool notInDestination(int sourceNum) {
	for (int i = 0; i < MAX_TANK_NUM; i++) {
		if (destination[i] == sourceNum + 1)
			return 0; //被定为目标了
	}
	return 1;
}
int calculateLength(short row1, short col1, short row2, short col2) {
	//return sqrt(abs(row1-row2)*abs(row1-row2)+abs(col1-col2)*abs(col1-col2));
	return abs(row1 - row2) + abs(col1 - col2);
}
bool compare(Item item1, Item item2) {
	if (item1.F < item2.F)
		return 1;
	else
		return 0;
}
bool haveEnemy(short row, short col, DataForAI data) {
	if (data.myFlag == RED && data.map[row][col].whoIsHere > 4)
		return 1;

	if (data.myFlag == BLUE && (0 <= data.map[row][col].whoIsHere
			&& data.map[row][col].whoIsHere <= 4))
		return 1;

	return 0;
}
short getPriceToPoint(short row, short col) {
	CellType cellType = gdata.map[row][col].type;
	short flag = 1;
	if(gdata.round<30) return 1;  //刚开始阶段，不需要仔细计算；
	switch (cellType) {
	case PERVIOUS:
		flag += 0;
		break;
	case BRICK:
		flag += 2/gdata.tank[gdata.myID].attack;
		break;
	case BREAKBRICK:
		flag += 1;
		break;
	case STONE:
		flag += 99;
		break;
	}
	return flag;
}
void updateField(DataForAI& data){ // 合并出视野
     if(data.round == roundCount)
        return;
     roundCount=data.round;
     for(int i=0;i<MAP_HEIGHT;i++)
        for(int j=0;j<MAP_WIDTH;j++)
               Field[i][j]=0;

              ////////本方坦克的视野
     int minTankNum=0;
     if(data.myFlag==BLUE) minTankNum=5;
     int count=5;
     while(count--){
             short row = data.tank[minTankNum].row;
             short col = data.tank[minTankNum].col;
                //(row,col)计算该坐标本方坦克的视野
                for(int i=-SIGHT;i<=SIGHT;i++)
                   for(int j=-SIGHT;j<=SIGHT;j++)
                      if((abs(i)+abs(j)<=SIGHT)&&(IsOk(row+i,col+j))) {
                              Field[row+i][col+j]=1;
                      }
             minTankNum++;
             }

      ////矿点的视野
     for(int k=0;k<data.totalSource;k++){
                short row = data.source[k].row;
                short col = data.source[k].col;

                for(int i=-SOURCE_SIGHT;i<=SOURCE_SIGHT;i++)
                   for(int j=-SOURCE_SIGHT;j<=SOURCE_SIGHT;j++)
                      if((abs(i)+abs(j)<=SOURCE_SIGHT)&&(IsOk(row+i,col+j)))
                              Field[row+i][col+j]=1;
    }

}

#define MAXN 442
int HeapSize;
Item Heap[MAXN+1];
void HeapUp(int p)
{
	int q=p>>1;
	Item a=Heap[p];
	while(q){
		if(a.F<Heap[q].F) Heap[p]=Heap[q];
		else break;
		p=q;
		q=p>>1;
	}
	Heap[p]=a;
}
void HeapDown(int p){
	int q=p<<1;
	Item a = Heap[p];
	while(q<=HeapSize){
		if(q<HeapSize&&Heap[q+1].F<Heap[q].F) q++;
		if(Heap[q].F < a.F) Heap[p]=Heap[q];
		else break;
		p=q;
		q=p<<1;
	}
	Heap[p]=a;
}

void AddToHeap(Item a){
	Heap[++HeapSize]=a;
	HeapUp(HeapSize);
}
Item GetTopFromHeap(){
	Item TopElement = Heap[1];
	Heap[1] = Heap[HeapSize--];
	HeapDown(1);
	return TopElement;
}
int FindPointInHeap(Point point){
	int index;
	if(HeapSize==0) index=0;
	else {
		for(index=1;index<=HeapSize;index++){
			if(Heap[index].row==point.row&&Heap[index].col==point.col) break;
		}
	}
	return index;
}

PathFindingResult pathFindingUsingAStar2(Point start, Point end){
	PathFindingResult pathFindingResult;
	short start_row = start.row;
	short start_col = start.col;
	short end_row = end.row;
	short end_col = end.col;
    //fout<<"start ("<<start_row<<","<<start_col<<")"<<endl;
	//fout<<"end ("<<end_row<<","<<end_col<<")"<<endl;

	if(start_row==end_row&&start_col==end_col){
		pathFindingResult.nextPoint=start;
		pathFindingResult.takeSourceStep=0;
	}else {

		//初始化堆
		HeapSize=0;
		bool closeList[MAP_HEIGHT + 1][MAP_WIDTH+ 1];
		for (int i = 0; i < MAP_HEIGHT + 1; i++)
			for (int j = 0; j < MAP_WIDTH + 1; j++)
					closeList[i][j] = 0;
		bool inOpenList[MAP_HEIGHT + 1][MAP_WIDTH + 1];
			for (int i = 0; i < MAP_HEIGHT + 1; i++)
				for (int j = 0; j < MAP_WIDTH + 1; j++)
					inOpenList[i][j] = 0;
		Item item;
		item.G = 0;
		item.H = abs(start_row - end_row) + abs(start_col - end_col);
		item.F = item.G + item.H;
		item.row = start_row;
		item.col = start_col;
		AddToHeap(item);
		inOpenList[item.row][item.col] = 1;

			Item objItem;

		Point parentItemList[MAP_HEIGHT + 1][MAP_WIDTH + 1];
		parentItemList[item.row][item.col].row = 0;
		parentItemList[item.row][item.col].col = 0;

		// A star

		while (HeapSize) {
			Item currentItem = GetTopFromHeap();
			inOpenList[currentItem.row][currentItem.col] = 0;
			closeList[currentItem.row][currentItem.col] = 1; // 放入closeList
			short currentItem_row = currentItem.row;
			short currentItem_col = currentItem.col;

			// (currentItem_row-1,currentItem_col)
			if ((gdata.map[currentItem_row - 1][currentItem_col].type == STONE)
					|| closeList[currentItem_row - 1][currentItem_col]) // 不可通过，或者已经在关闭的列表中
			{
				// do nothing
			} else {
				if (!inOpenList[currentItem_row - 1][currentItem_col]) {
					Item newItem;
					newItem.row = currentItem_row - 1;
					newItem.col = currentItem_col;
					newItem.H = abs(currentItem_row - 1 - end_row) + abs(
							currentItem_col - end_col);
					newItem.G = currentItem.G + getPriceToPoint(currentItem_row-1,currentItem_col);
					newItem.F = newItem.G + newItem.H;

					parentItemList[newItem.row][newItem.col].row = currentItem.row;
					parentItemList[newItem.row][newItem.col].col = currentItem.col;
					AddToHeap(newItem);
					inOpenList[newItem.row][newItem.col] = 1;
					if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
					{
						objItem = newItem;
						break;
					}
				} else {
					Point point;
					point.row = currentItem_row-1;
					point.col = currentItem_col;
					int index = FindPointInHeap(point);
					int G = currentItem.G + getPriceToPoint(currentItem_row-1,currentItem_col);
					if (G < Heap[index].G) {
						Heap[index].G = G;
						Heap[index].F = Heap[index].G + Heap[index].H;
						parentItemList[Heap[index].row][Heap[index].col].row = currentItem.row;
						parentItemList[Heap[index].row][Heap[index].col].col = currentItem.col;
						HeapUp(index);
					}
				}
			}
			//(currentItem_row+1,currentItem_col) /

			if ((gdata.map[currentItem_row + 1][currentItem_col].type == STONE)
								|| closeList[currentItem_row + 1][currentItem_col]) // 不可通过，或者已经在关闭的列表中
						{
							// do nothing
						} else {
							if (!inOpenList[currentItem_row +1][currentItem_col]) {
								Item newItem;
								newItem.row = currentItem_row + 1;
								newItem.col = currentItem_col;
								newItem.H = abs(currentItem_row + 1 - end_row) + abs(
										currentItem_col - end_col);
								newItem.G = currentItem.G + getPriceToPoint(currentItem_row+1,currentItem_col);
								newItem.F = newItem.G + newItem.H;

								parentItemList[newItem.row][newItem.col].row = currentItem.row;
								parentItemList[newItem.row][newItem.col].col = currentItem.col;
								AddToHeap(newItem);
								inOpenList[newItem.row][newItem.col] = 1;
								if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
								{
									objItem = newItem;
									break;
								}
							} else {
								Point point;
								point.row = currentItem_row+1;
								point.col = currentItem_col;
								int index = FindPointInHeap(point);
								int G = currentItem.G + getPriceToPoint(currentItem_row+1,currentItem_col);
								if (G < Heap[index].G) {
									Heap[index].G = G;
									Heap[index].F = Heap[index].G + Heap[index].H;
									parentItemList[Heap[index].row][Heap[index].col].row = currentItem.row;
									parentItemList[Heap[index].row][Heap[index].col].col = currentItem.col;
									HeapUp(index);
								}
							}
						}
			//(currentItem_row,currentItem_col-1)
			if ((gdata.map[currentItem_row][currentItem_col-1].type == STONE)
								|| closeList[currentItem_row ][currentItem_col- 1]) // 不可通过，或者已经在关闭的列表中
						{
							// do nothing
						} else {
							if (!inOpenList[currentItem_row][currentItem_col- 1]) {
								Item newItem;
								newItem.row = currentItem_row;
								newItem.col = currentItem_col- 1;
								newItem.H = abs(currentItem_row - end_row) + abs(
										currentItem_col - 1- end_col);
								newItem.G = currentItem.G +getPriceToPoint(currentItem_row,currentItem_col-1);
								newItem.F = newItem.G + newItem.H;

								parentItemList[newItem.row][newItem.col].row = currentItem.row;
								parentItemList[newItem.row][newItem.col].col = currentItem.col;
								AddToHeap(newItem);
								inOpenList[newItem.row][newItem.col] = 1;
								if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
								{
									objItem = newItem;
									break;
								}
							} else {
								Point point;
								point.row = currentItem_row;
								point.col = currentItem_col- 1;
								int index = FindPointInHeap(point);
								int G = currentItem.G + getPriceToPoint(currentItem_row,currentItem_col-1);
								if (G < Heap[index].G) {
									Heap[index].G = G;
									Heap[index].F = Heap[index].G + Heap[index].H;
									parentItemList[Heap[index].row][Heap[index].col].row = currentItem.row;
									parentItemList[Heap[index].row][Heap[index].col].col = currentItem.col;
									HeapUp(index);
								}
							}
						}
			///(currentItem_row,currentItem_col+1)
			if ((gdata.map[currentItem_row][currentItem_col+1].type == STONE)
								|| closeList[currentItem_row][currentItem_col+1]) // 不可通过，或者已经在关闭的列表中
						{
							// do nothing
						} else {
							if (!inOpenList[currentItem_row][currentItem_col+1]) {
								Item newItem;
								newItem.row = currentItem_row;
								newItem.col = currentItem_col+1;
								newItem.H = abs(currentItem_row - end_row) + abs(
										currentItem_col+1 - end_col);
								newItem.G = currentItem.G + getPriceToPoint(currentItem_row,currentItem_col+1);
								newItem.F = newItem.G + newItem.H;

								parentItemList[newItem.row][newItem.col].row = currentItem.row;
								parentItemList[newItem.row][newItem.col].col = currentItem.col;
								AddToHeap(newItem);
								inOpenList[newItem.row][newItem.col] = 1;
								if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
								{
									objItem = newItem;
									break;
								}
							} else {
								Point point;
								point.row = currentItem_row;
								point.col = currentItem_col+1;
								int index = FindPointInHeap(point);
								int G = currentItem.G + getPriceToPoint(currentItem_row,currentItem_col+1);
								if (G < Heap[index].G) {
									Heap[index].G = G;
									Heap[index].F = Heap[index].G + Heap[index].H;
									parentItemList[Heap[index].row][Heap[index].col].row = currentItem.row;
									parentItemList[Heap[index].row][Heap[index].col].col = currentItem.col;
									HeapUp(index);
								}
							}
						}

			//////////////////////////

		} // while


		if(HeapSize==0){ //未找到路径
			Point nextStep_point;
			nextStep_point.row = start.row;
			nextStep_point.col = start.col;
			pathFindingResult.nextPoint = nextStep_point;
			pathFindingResult.takeSourceStep = 0;
		}else {
			Item aItem = objItem;
			//fout<<aItem.row<<"  "<<aItem.col<<endl;
			int takeSourceStep=1;
			while (!(parentItemList[aItem.row][aItem.col].row == start_row
					&& parentItemList[aItem.row][aItem.col].col == start_col)
					&& (parentItemList[aItem.row][aItem.col].row != 0)
					&& (parentItemList[aItem.row][aItem.col].col != 0)) {
				takeSourceStep++;
				short row = aItem.row;
				short col = aItem.col;
				aItem.row = parentItemList[row][col].row;
				aItem.col = parentItemList[row][col].col;
			}

			Point nextStep_point;
			nextStep_point.row = aItem.row;
			nextStep_point.col = aItem.col;

			pathFindingResult.nextPoint = nextStep_point;
			pathFindingResult.takeSourceStep = takeSourceStep;
			}
	}



	return pathFindingResult;
}


PathFindingResult pathFindingUsingAStar(Point start_point, Point end_point,
		DataForAI data) {
	short start_row = start_point.row;
	short start_col = start_point.col;
	short end_row = end_point.row;
	short end_col = end_point.col;
	PathFindingResult pathFindingResult;

	if (start_row == end_row && start_col == end_col) {
		pathFindingResult.nextPoint = start_point;
		pathFindingResult.takeSourceStep = 0;
		return pathFindingResult;
	}

	int takeSourceStep = 1;
	Point nextStep_point;

	//short flag = 0;

	list<Item> openList;
	bool closeList[MAP_HEIGHT + 1][MAP_WIDTH+ 1];
	for (int i = 0; i < MAP_HEIGHT + 1; i++)
		for (int j = 0; j < MAP_WIDTH + 1; j++)
			closeList[i][j] = 0;
	bool inOpenList[MAP_HEIGHT + 1][MAP_WIDTH + 1];
	for (int i = 0; i < MAP_HEIGHT + 1; i++)
		for (int j = 0; j < MAP_WIDTH + 1; j++)
			inOpenList[i][j] = 0;
	Item item;
	item.G = 0;
	item.H = abs(start_row - end_row) + abs(start_col - end_col);
	item.F = item.G + item.H;
	item.row = start_row;
	item.col = start_col;
	openList.push_back(item);
	inOpenList[item.row][item.col] = 1;

	Item objItem; //end point item

	Point parentItemList[MAP_HEIGHT + 1][MAP_WIDTH + 1];
	parentItemList[item.row][item.col].row = 0;
	parentItemList[item.row][item.col].col = 0;


	short minTank = 0;
	short maxTank = 4;
	if (gdata.myFlag == BLUE) {
		minTank = 5;
		maxTank = 9;
	}
	//int a=0;
	while (!openList.empty()) {

		//if(gdata.round==56&&gdata.myID==3&&(a>30))
      // a++;

		openList.sort(compare);
		Item currentItem = openList.front();
		openList.pop_front();
		inOpenList[currentItem.row][currentItem.col] = 0;
		closeList[currentItem.row][currentItem.col] = 1; // 放入closeList
		short currentItem_row = currentItem.row;
		short currentItem_col = currentItem.col;

		// (currentItem_row-1,currentItem_col)  // (minTank<=data.map[currentItem_row-1][currentItem_col].whoIsHere&&data.map[currentItem_row-1][currentItem_col].whoIsHere<=maxTank)
		if ((data.map[currentItem_row - 1][currentItem_col].type == STONE)
				|| closeList[currentItem_row - 1][currentItem_col]) // 不可通过，或者已经在关闭的列表中
		{
			// do nothing
		} else {
			if (!inOpenList[currentItem_row - 1][currentItem_col]) {
				Item newItem;
				newItem.row = currentItem_row - 1;
				newItem.col = currentItem_col;
				newItem.H = abs(currentItem_row - 1 - end_row) + abs(
						currentItem_col - end_col);
				newItem.G = currentItem.G + getPriceToPoint(
						currentItem_row - 1, currentItem_col);
				newItem.F = newItem.G + newItem.H;

				parentItemList[newItem.row][newItem.col].row = currentItem.row;
				parentItemList[newItem.row][newItem.col].col = currentItem.col;
				openList.push_back(newItem);
				inOpenList[newItem.row][newItem.col] = 1;
				if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
				{
					objItem = newItem;
					break;
				}
			} else {
				list<Item>::iterator it = openList.begin();
				for (; it != openList.end(); it++) {
					Item xxxItem = *it;
					if ((xxxItem.row == currentItem_row - 1) && (xxxItem.col
							== currentItem_col))
						break;
				}
				int G = currentItem.G + getPriceToPoint(currentItem_row - 1,
						currentItem_col);
				if (G < (*it).G) {
					(*it).G = G;
					(*it).F = (*it).G + (*it).H;
					parentItemList[(*it).row][(*it).col].row = currentItem.row;
					parentItemList[(*it).row][(*it).col].col = currentItem.col;
				}
			}
		}
		//(currentItem_row+1,currentItem_col) //(minTank<=data.map[currentItem_row+1][currentItem_col].whoIsHere&&data.map[currentItem_row+1][currentItem_col].whoIsHere<=maxTank)||
		if ((data.map[currentItem_row + 1][currentItem_col].type == STONE)
				|| closeList[currentItem_row + 1][currentItem_col]) // 不可通过，或者已经在关闭的列表中
		{
			// do nothing
		} else {
			if (!inOpenList[currentItem_row + 1][currentItem_col]) {
				Item newItem;
				newItem.row = currentItem_row + 1;
				newItem.col = currentItem_col;
				newItem.H = abs(currentItem_row + 1 - end_row) + abs(
						currentItem_col - end_col);
				newItem.G = currentItem.G + getPriceToPoint(
						currentItem_row + 1, currentItem_col);

				newItem.F = newItem.G + newItem.H;
				parentItemList[newItem.row][newItem.col].row = currentItem.row;
				parentItemList[newItem.row][newItem.col].col = currentItem.col;
				openList.push_back(newItem);
				inOpenList[newItem.row][newItem.col] = 1;
				if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
				{
					objItem = newItem;
					break;
				}
			} else {
				list<Item>::iterator it = openList.begin();
				for (; it != openList.end(); it++) {
					if (((*it).row == currentItem_row + 1) && ((*it).col
							== currentItem_col))
						break;
				}
				int G = currentItem.G + getPriceToPoint(currentItem_row + 1,
						currentItem_col);
				if (G < (*it).G) {
					(*it).G = G;
					(*it).F = (*it).G + (*it).H;
					parentItemList[(*it).row][(*it).col].row = currentItem.row;
					parentItemList[(*it).row][(*it).col].col = currentItem.col;
				}
			}
		}

		// (currentItem_row,currentItem_col-1)  //(minTank<=data.map[currentItem_row][currentItem_col-1].whoIsHere&&data.map[currentItem_row][currentItem_col-1].whoIsHere<=maxTank)||
		if ((data.map[currentItem_row][currentItem_col - 1].type == STONE)
				|| closeList[currentItem_row][currentItem_col - 1]) // 不可通过，或者已经在关闭的列表中
		{
			// do nothing
		} else {
			if (!inOpenList[currentItem_row][currentItem_col - 1]) {
				Item newItem;
				newItem.row = currentItem_row;
				newItem.col = currentItem_col - 1;
				newItem.H = abs(currentItem_row - end_row) + abs(
						currentItem_col - 1 - end_col);
				newItem.G = currentItem.G + getPriceToPoint(currentItem_row,
						currentItem_col - 1);

				newItem.F = newItem.G + newItem.H;
				parentItemList[newItem.row][newItem.col].row = currentItem.row;
				parentItemList[newItem.row][newItem.col].col = currentItem.col;
				openList.push_back(newItem);
				inOpenList[newItem.row][newItem.col] = 1;
				if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
				{
					objItem = newItem;
					break;
				}
			} else {
				list<Item>::iterator it = openList.begin();
				for (; it != openList.end(); it++) {
					if (((*it).row == currentItem_row) && ((*it).col
							== currentItem_col - 1))
						break;
				}
				int G = currentItem.G + getPriceToPoint(currentItem_row,
						currentItem_col - 1);
				if (G < (*it).G) {
					(*it).G = G;
					(*it).F = (*it).G + (*it).H;
					parentItemList[(*it).row][(*it).col].row = currentItem.row;
					parentItemList[(*it).row][(*it).col].col = currentItem.col;
				}
			}
		}

		// (currentItem_row,currentItem_col+1)  //(minTank<=data.map[currentItem_row][currentItem_col+1].whoIsHere&&data.map[currentItem_row][currentItem_col+1].whoIsHere<=maxTank)||
		if ((data.map[currentItem_row][currentItem_col + 1].type == STONE)
				|| closeList[currentItem_row][currentItem_col + 1]) // 不可通过，或者已经在关闭的列表中
		{
			// do nothing
		} else {
			if (!inOpenList[currentItem_row][currentItem_col + 1]) {
				Item newItem;
				newItem.row = currentItem_row;
				newItem.col = currentItem_col + 1;
				newItem.H = abs(currentItem_row - end_row) + abs(
						currentItem_col + 1 - end_col);
				newItem.G = currentItem.G + getPriceToPoint(currentItem_row,
						currentItem_col + 1);

				newItem.F = newItem.G + newItem.H;
				parentItemList[newItem.row][newItem.col].row = currentItem.row;
				parentItemList[newItem.row][newItem.col].col = currentItem.col;
				openList.push_back(newItem);
				inOpenList[newItem.row][newItem.col] = 1;
				if ((newItem.row == end_row) && (newItem.col == end_col)) //目标被加入到openList中，结束
				{
					objItem = newItem;
					break;
				}
			} else {
				list<Item>::iterator it = openList.begin();
				for (; it != openList.end(); it++) {
					if (((*it).row == currentItem_row) && ((*it).col
							== currentItem_col + 1))
						break;
				}
				int G = currentItem.G + getPriceToPoint(currentItem_row,
						currentItem_col + 1);
				if (G < (*it).G) {
					(*it).G = G;
					(*it).F = (*it).G + (*it).H;
					parentItemList[(*it).row][(*it).col].row = currentItem.row;
					parentItemList[(*it).row][(*it).col].col = currentItem.col;
				}
			}
		}
		//////////////////////////

	} // while
   // fout<<a<<endl;

	// 形成下一步

//	if(openList.empty())
//	{
//		nextStep_point.row = start_row;
//		nextStep_point.col = start_col;
//		pathFindingResult.nextPoint = nextStep_point;
//		pathFindingResult.takeSourceStep=1000; //暂时没找到路径，停一回合； takeSourceStep赋值较高，为了该指令尽量不执行
//	}
//	else {

		Item aItem = objItem;

		while (!(parentItemList[aItem.row][aItem.col].row == start_row
				&& parentItemList[aItem.row][aItem.col].col == start_col)
				&& (parentItemList[aItem.row][aItem.col].row != 0)
				&& (parentItemList[aItem.row][aItem.col].row != 0)) {
			takeSourceStep++;
			short row = aItem.row;
			short col = aItem.col;
			aItem.row = parentItemList[row][col].row;
			aItem.col = parentItemList[row][col].col;
		}

		nextStep_point.row = aItem.row;
		nextStep_point.col = aItem.col;

		pathFindingResult.nextPoint = nextStep_point;
		pathFindingResult.takeSourceStep = takeSourceStep;
	//}
	return pathFindingResult;
}
